// https://leetcode-cn.com/problems/course-schedule/
// 207. Course Schedule
// There are a total of `numCourses` courses you have to take, labeled from `0` to
// `numCourses - 1`. You are given a array `prerequisites` where
// `prerequisites[i] = [ai, bi]` indicates that you must take course `bi`
// first if you want to take course `ai`
// For example, the pair [0, 1], indicates that to take course 0 you have
// to first take course 1
// Return true if you can finish all courses. Otherwise, return false
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const visited: number[] = new Array(numCourses).fill(0);
    const map: Map<number, number[]> = new Map();
    let valid: boolean = true;

    for (const [child, parent] of prerequisites) {
        const result = map.get(parent) || [];
        map.set(parent, result.concat(child));
    }

    for (let i = 0; i < numCourses && valid; i++) {
        if (visited[i] === 0) {
            dfs(i);
        }
    }

    return valid;

    function dfs(u: number): void {
        visited[u] = 1;
        for (const v of map.get(u) || []) {
            if (visited[v] === 0) {
                dfs(v);
                if (!valid) return;
            } else if (visited[v] === 1) {
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
}
